package btree.base;

/**
 * 给定递增序列构造平衡二叉树
 */
public class SortedArrayToBST {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildBST(nums, 0, nums.length - 1);
    }

    /**
     * 把数组 中间元素提起来当根，左边递归做左子树，右边递归做右子树。这样左右节点数量差 ≤1，天然平衡。
     */
    private TreeNode buildBST(int[] nums, int left, int right) {
        if (left > right) return null;  // 终止条件
        int mid = (left+right)>>>1;  // 防止溢出
        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildBST(nums, left, mid - 1);  // 递归构建左子树
        root.right = buildBST(nums, mid + 1, right);  // 递归构建右子树
        return root;
    }

    // 测试代码：验证是否为平衡BST
    public boolean isBalanced(TreeNode root) {
        return checkHeight(root) != -1;
    }

    private int checkHeight(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = checkHeight(root.left);
        if (leftHeight == -1) return -1;  // 左子树不平衡
        int rightHeight = checkHeight(root.right);
        if (rightHeight == -1) return -1;  // 右子树不平衡
        if (Math.abs(leftHeight - rightHeight) > 1) return -1;  // 当前节点不平衡
        return Math.max(leftHeight, rightHeight) + 1;
    }

    // 中序遍历验证BST性质
    public void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    // 测试用例
    public static void main(String[] args) {
        SortedArrayToBST solution = new SortedArrayToBST();
        int[] nums = {-10, -3, 0, 5, 9};  // 严格递增序列
        TreeNode root = solution.sortedArrayToBST(nums);

        System.out.print("中序遍历结果（验证BST性质）: ");
        solution.inorder(root);  // 应输出有序序列
        System.out.println("\n是否为平衡BST: " + solution.isBalanced(root));  // 应输出true
    }
}